package com.example.leetcode.math;

/**
 * 你总共有 n 枚硬币，并计划将它们按阶梯状排列。对于一个由 k 行组成的阶梯，其第 i 行必须正好有 i 枚硬币。阶梯的最后一行 可能 是不完整的。
 *
 * 给你一个数字 n ，计算并返回可形成 完整阶梯行 的总行数。
 */
public class leetcode441 {
    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.arrangeCoins(2147483647));
    }

    static class Solution {
//        public int arrangeCoins(int n) {
//            int level = 0;
//            while (n >= level + 1) {
//                level++;
//                n -= level;
//            }
//            return level;
//        }

        public int arrangeCoins(int n) {
            long left = 0, right = n;
            while (left <= right) {
                long mid = left + (right - left) / 2;
                long sum = mid * (mid + 1) / 2;
                if (sum == n) return (int) mid;
                if (sum < n) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
            return (int) right;
        }

    }
}
